# @Author：Kilien
# @lc app=leetcode id=236 lang=python3
#
# [236] Lowest Common Ancestor of a Binary Tree
# 思路：
# 先决条件：若root为空或者等于某个目标节点，返回root
# Divide：遍历左右子树
# Conquer：若左右子树皆有返回值，则root为最小公共祖先
# 若只有左子树有返回值，则左子树的返回值为最小公共祖先
# 若只有右子树有返回值，则右子树的返回值为最小公共祖先
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None: 
            return root
        if root == p or root == q:
            return root

        #Divide
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        #Conquer
        if left is None:
            return right 
        elif right is None:
            return left 
        else:
            return root

